Since a communication channel is subject to various types of noise, distortion, and interference, the output of the channel tends to differ from its input. Error-correcting coding is employed in digital communications systems to reduce the average probability of errors that occur during data transmission. For example, a mixture of burst errors and random errors can affect communication channels in a digital satellite communications system. Fading effects, jamming, or crosstalk may cause transmission errors that occur in bursts, when noise affects up to a few transmitted bytes. Random errors may result from noise that affects each transmitted digit independently.
Concatenated codes are effective against a mixture of random and burst errors in digital satellite communications. Concatenated coding introduced in 1966 implements a code with a very long block length and large error-correcting capability by utilizing multiple levels of coding. The most common approach uses inner and outer codes to provide two levels of coding. Reed-Solomon (RS) codes are used as the outer code, whereas convolutional codes may be used as the inner code. Scattered random errors in a received word are correctable by the inner code. Burst errors can then be corrected by the outer code.
Referring to FIG. 1, a digital satellite communications system 100 employing a concatenated code may comprise an outer RS encoder 2 that receives data from a data source to provide outer RS encoding. RS encoded data from the RS encoder 2 are supplied to an interleaver 4 that reorders the encoded data in a deterministic manner to enable use of a deinterleaver for spreading out error bursts in time so that errors within a code word are isolated. The interleaver 4 may be a block interleaver that formats the encoded data in a rectangular array of m rows and n columns. Each row of the array constitutes a code word of length n. The bits of the RS encoded data are read out column-wise. As a result, a burst of errors of length l=mb can be broken up into m bursts of length b. The interleaved data are supplied to an inner convolutional encoder 6 that generates convolutional coded data. The convolutional encoder 6 may be a finite-state shift register that consists of multiple k-bit stages. The input data to the convolutional encoder are shifted into and along the shift register k bits at a time to generate an output bit stream. A modulator 8 modulates the encoded data to enable data transmission over a channel 10.
At a receiver, a demodulator 12 demodulates the received data and supplies them to a Viterbi decoder 14 that provides decoding of a convolutional code. The decoder 14 implements the Viterbi algorithm, which is a maximum likelihood decoding algorithm for convolutional codes. This decoding algorithm introduced in 1967 uses the trellis structure of the code and determines the maximum-likelihood estimate of the transmitted code word that has the largest metric. The likelihood function represents the metric which can be computed for each path in the trellis. The Viterbi decoder 14 finds the path with the largest accumulated metric through the trellis in such a way that it processes the received word in an iterative manner. At each step, it compares the metrics of all paths entering each state, stores only the path with the largest accumulated metric, and discards the unlikely paths at every state, which reduces the decoding effort.
A deinterleaver 16 coupled to the Viterbi decoder 14 uses inverse permutation to restore the bit sequence reordered by the interleaver 4 to the original order. The deinterleaver 16 stores the data in the same rectangular array format as the interleaver 4. The data are read out row-wise, one code word of length n at a time.
As a result, m bursts of the code words are supplied to an outer RS decoder 18 that may implement, for example, the Berlekamp-Massey decoding algorithm to provide RS decoding. The RS decoder 18 detects errors and generates syndrome bytes S(x) for each received codeword. An extended Euclidean algorithm is used to find an error location polynomial .sigma.(x) and error value polynomial .eta.(x). The Chien Search process may be implemented to find actual error locations based on the error location polynomial .sigma.(x).
The error value polynomial .eta.(x) and error locations determined based on the error location polynomial .sigma.(x) are used to determine an error value at each error location found by the Chien Search process. The determined error locations and values are used to correct the errors.
If the data supplied to the RS decoder 18 includes erasures, the decoder 18 performs polynomial expansion to find the erasure polynomial based on known erasure locations. Modulo polynomial multiplication is carried out to calculate modified syndrome polynomial used in regular polynomial multiplication to obtain the erasure/error location polynomial. The RS and convolutional encoding and decoding, including the Viterbi and Berlekamp-Massey decoding algorithms, are described in more detail in numerous textbooks and publications, for example, in Error Control Coding: Fundamentals and Applications, by S. Lin and D. J. Costello, Jr., Prentice-Hall, Englewood Cliffs, N.J., 1983, or Error Correcting Coding Theory, by Man Young Rhee, McGraw-Hill Publishing Company, 1989, incorporated herein by reference.
The disclosed concatenated coding arrangement may be used, for example, in a digital satellite television system that includes a transmitter for transmitting television signals to a satellite in a geosynchronous earth orbit. The satellite retransmits the received television signals to a terrestrial receiver equipped with a dish-like antenna.
Within the transmitter, analog video and audio signals are converted to respective digital signals compressed and encoded according to the Motion Picture Expert Group (MPEG) compression and encoding standard. The resultant digital signals are represented by a stream of packets including error correction data. The transmitter employs Viterbi and RS coding to form the error correction data.
The terrestrial receiver comprises Viterbi and RS decoders to decode the codewords retransmitted by the satellite. Video and audio decoders decode and decompress video and audio packets of the error corrected signals to form digital video and audio signals supplied to a TV set.
As discussed above, scattered random errors in received data are corrected by the Viterbi decoder, whereas the RS decoder corrects burst errors. The RS decoder employs a t-error correcting RS code capable of correcting any error pattern that affects t or fewer bytes. For example, for an MPEG2 format, up to 8 bytes can be corrected in an 188-byte data block. For a Digital Satellite System (DSS) format, an RS code is able to correct 8 bytes in a 146-byte data block. It is immaterial whether one bit error exists in a corrupted byte, or a corrupted byte contains several bit errors. The error is still counted as one byte error. Thus, only t corrupted bytes may be corrected in an error correction mode. However, as well known in the art and illustrated, for example, in the S. Lin and D. J. Costello, Jr. textbook, a t-error correcting RS code is able to correct up to 2t erased bytes in an erasure correcting mode.
Therefore, to increase the error-correcting capability of a coding system, it would be desirable to provide an arrangement that allows errors to be decoded by an RS decoder in an erasure correcting mode.